1. Field of the Invention
The present invention relates to a system and method for determining a level of similarity among more than one image and a segmented data structure for enabling such determination. More particularly, the present invention relates to a system and method in which anticipated spatial characteristics of an image are used for automatically identifying segments within the image and for identifying weights to be applied to the color characteristics associated with the identified segments, and to a data structure having a color descriptor field in which plural segments are defined to represent color characteristics of corresponding segments identified in the image.
2. Description of the Related Art
Color is one of the most straightforward and intuitive characteristics to represent an image. For this reason, color histograms have been widely adopted as feature descriptors for images.
To characterize images based on color, conventional systems compute color histograms based on the global color characteristics of an entire image. Specifically, as shown by FIG. 2, conventional systems compute color histograms globally for an image, compute similarity functions to compare color histograms of different images, and detect similarity based on the computed similarity function. Although the histograms computed by these systems provide useful information about the global color content of an image, they fail to provide any spatial information. It is therefore possible for more than one image to have similar color histograms even though those images differ drastically, as demonstrated by FIGS. 1A-1B and 1C-1D.
Other conventional systems segment an image into predetermined areas having standard sizes before computing color histograms. These systems compute color histograms for each of the segmented areas, compute similarity functions to compare color characteristics of corresponding segments within different images, and detect similarity based on the similarity function, as shown in FIG. 3A. However, by segmenting the image into predetermined areas, these systems fail to take advantage of anticipated spatial .characteristics of the image such as the anticipated positioning of objects of interest. Furthermore, these systems generally rely on increasing in the number of segments to increase precision, resulting in increased computational complexity and cross-over noise.
FIGS. 3B and 3C illustrate two conventional systems that identify a predetermined number of standard-sized segments without regard for the anticipated spatial characteristics of an image being processed. The system of FIG. 3B identifies a predetermined number of standard-sized segments (e.g., 64) for any input image, calculates color characteristics within each of the standard-sized segments, and compares the color characteristics of each segment of an image with corresponding segments of other images to determine similarity.
The system of FIG. 3C is somewhat more complex. In the system of FIG. 3, an image is divided into a number of fixed-sized segments, color characteristics of each segment are computed, and the color characteristics of those segments are compared to the color characteristics of other segments within that image. If color characteristics of two or more segments exceed threshold similarity, those segments are merged. Otherwise, the segments are further segmented, each into a second predetermined number of standard-sized subsegments, as shown. Color characteristics are then computed for each subsegment within the non-merged segments, and those color characteristics are compared to the color characteristics of each merged segment and subsegment. If the color characteristics of any subsegment and the color characteristics of any other subsegment or merged segment exceed the threshold similarity, they are merged to form a new merged segment. Otherwise, they are further segmented and compared in an iterative fashion.
As described, the systems of FIGS. 3B and 3C fail to identify segments based on anticipated spatial characteristics of an image. In fact, rather than account for the anticipated spatial characteristics of an image, these systems simply divide the image space into a predetermined number or pattern of standard-sized segments.
FIGS. 4A and 4B describe yet another conventional system for comparing images based on color. FIG. 4A is a flow chart describing this system. In FIG. 4A, objects are identified in step 401, segments are identified in step 402 based on the identified objects, color characteristics are computed in step 403 and similarity is detected in step 404. Unlike the conventional systems described with respect to FIGS. 2 and 3A-3C, the system of FIGS. 4A-4B is not limited to segments of fixed size, position or number. However, the system of FIGS. 4A-4B is also problematic. For instance, the conventional system of FIGS. 4A-4B is not easily implemented due to difficulties with automatic object detection techniques. Thus, manual or semi-manual segmentation is generally required by the conventional system of FIGS. 4A-4B. Furthermore, like the other conventional systems of FIGS. 2-3C, the system of FIGS. 4A-4B also fails to take advantage of anticipated spatial characteristics when identifying segments within the image space, instead relying on detection of spatial features in each particular image being characterized.
An object of this invention is to describe the color characteristics of images based on anticipated spatial information within those images.
Another object of this invention is to recursively decompose an image into fixed or varied size segments based on anticipated spatial information. Therefore, the color histograms are computed and compared with color histograms of corresponding segments of other images, preferably via a weighted similarity matrix, to determine similarity.
To accomplish this and other objects, the present invention includes a method for determining similarity among more than one image by automatically identifying segments within an image which have attributes based on spatial characteristics of the image, and comparing color characteristics of the image data within the identified segments of the image to color characteristics of the image data within corresponding segments of at least one other image to determine similarity among the images. At least one of the identified segments may overlap other of the identified segments.
Biasing may be performed to achieve greater emphasis for comparisons of color characteristics between selected segments within the images. Weights used to achieve biasing are determined based on the anticipated spatial characteristics. A similarly among the images is determined based on the results of the comparison reflecting the bias.
The anticipated spatial characteristics of the image include differences in image characteristics that are anticipated at relative positions with the image. The anticipated spatial characteristics of the image may also include at least one of an anticipated position of an object within the image and an anticipated difference in coloration between two positions of the image. The attributes of the identified segments include at least one of number, position and size of segments. The size of segments is non-uniform so as to apply unequal emphasis on features within the image being characterized.
The automatic identification of segments may be performed by recursively identifying segments within the image. The number of iterations of the recursive identification of segments is generally determined based on a variance detected among color characteristics of image data within segments previously identified.
The color characteristics are compared to determine an occurrence of change in image characteristics or to identify similar images.
In addition, the present invention includes a data structure that includes fields specifying color descriptors for segments within an image, and standards adopting such a data structure.
Further scope of applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, wile indicating preferred embodiments of the invention, are given by way of example only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.